模拟赛题解/2025.10.23 模拟赛

T1-Wei 子与 Runs（runs）

题面

Wei 子现在得到了一个仅由小写字母构成的字符串 $S$，他把每一个极长连续相同字符子段称作一个“段”（runs），他现在想问你有多少种不同的排列这个字符串的方案使得新的字符串段数和 $S$ 相同。

由于答案可能很大，答案对 $10^9 + 7$ 取模。 我们定义两个字符串 $A, B$ 不同当且仅当 $\exists i, A_i \neq B_i$。

$1\leq n\leq10^6$。

题解

先记录下每种字符出现数，记为 $cnt$，搞个前缀和 $sum$。

直接设 $dp_{i,j}$ 表示考虑了前 $i$ 种字符，有 $j$ 个连续段的方案数。

转移闭着眼睛整，枚举当前字符有多少段加在原来连续段间（加一段连续段数 +1），多少段在连续段中（加一段连续段数 +2），瞎乘个选择插入位置数，分配字符方案数了事，式子如下：

$dp_{i,j+k+2s} + = dp_{i-1,j} \times C_{sum_{i-1-j}}^s \times C_{j+1}^k \times C_{cnt_i}^{k+s-1}$

时间复杂度 $O(n + 26 \times 100^3)$。

T2-Wei 子与工厂（factory）

题面

Wei 子现在雇佣了 $n$ 个工人给 $n$ 台机器做工，每台机器都需要恰好一名工人来操作，才能保证工厂正常运转。

在招聘时 Wei 子得知 $j \in [1, n]$，第 $i$ 个工人是否会操作第 $j$ 台机器。

每天，工人都会以随机顺序到达工厂并随机选用当前没有人使用且他会操作的机器开始工作。

Wei 子现在可以花费 1 元钱培训 1 个工人学会操作 1 个机器。

作为大资本家，小 W 不希望出现工厂无法运作的现象，现在他问你最少花费多少元钱使得无论如何工厂都可以正常运转。

$1\leq t\leq100,1\leq n\leq25$。

题解

显然把工人和机器的关系视作一个二分图。

考虑这个二分图合法必然满足任意匹配都可以得到一组完美匹配。

考虑什么样的二分图是合法的。

可以发现必须每个连通块都满足两部分点数相同且是完全二分图。

充分性显然，必要性考虑反证，假设存在一个不符合我们上面条件的二分图但是合法。

我们在一个连通块 $G$ 内找两个没有直接连边的左部点和右部点 $u, v$ 。

考虑去掉这两个点后的图。

如果还有完美匹配，直接用这个匹配，此时 $u, v$ 均无法匹配，爆掉了；

否则根据 Hall 定理，去掉 $u, v$ 时左侧必然存在一个点集 $S$ 使得和它相邻的右部点集 $S'$ 大小比它小，由于 $G$ 联通，$S'$ 中必然有点和 $S$ 外的点相邻，直接将这样的点和 $S$ 外点匹配掉 $S$ 就爆掉了。

好的现在我们再来看题目要我们做什么。

原来有连边的部分必须分在一起，即你有一些左右部点数对 $(a_i, b_i)$，你需要把它们拼成左右部点数相同的点对，代价是单边点数的平方和减去边数。

此时直接开搜，对剩下点数对记忆化，每次暴力枚举一些集合合成一个左右部点数相同的点对即可。

可以发现本质不同状态数是少的，最坏 43008 个，可以通过。

T3-Wei 子与钥匙（key）

题面

有 $n$ 个箱子，每个箱子都只能用某种特定类型的钥匙打开，打开后那把钥匙就不能使用了，箱子中可能放着一些钥匙，打开后你就可以获得该箱子内的钥匙。

现在你初始有 $k$ 把钥匙，问你可不可能打开所有箱子，如果可能，输出字典序最小的打开所有箱子的方案。

这里，我们称一个方案为一个 $1 \sim n$ 的排列 $p$，使得我们能够按照编号 $p_1, p_2, ..., p_n$ 的顺序依次打开箱子。

$1\leq t\leq25,1\leq n\leq200,1\leq k+\sum s_i\leq400$。

题解

注意到我们本质上是要在知道我们当前有哪些钥匙，有哪些箱子的情况下判断是否有解，构造最小化方案只需要我们枚举当前开哪个箱子后判断剩下箱子是否有解即可。

考虑你最开始有一把钥匙，每个箱子内恰好有一把钥匙的情况。

把钥匙的种类视作点，一个箱子视作开箱子类型钥匙和打开后获得钥匙之间的边，题意就变成了指定点出发欧拉路径。

但是如果一个箱子里有多把钥匙，问题就不是欧拉路径了，考虑寻找一个图有解的情况：

• 当每类钥匙的总数大于等于需要使用的数量，且可以获取需要用的每种钥匙（上图从最开始拥有钥匙对应节点 BFS 可达），我们声称这是必然有解的。

• 必要性是显然的，充分性就是我们要说明始终存在一个可以打开的箱子，打开后不影响连通性。

你当前图满足：

对于任意需要的钥匙类型 $s$，存在一个钥匙种类序列 $k_1, k_2, ..., k_m$，其中 $k_1$ 为你当前手上拥有的钥匙，$k_m = s$，$k_{i+1}$ 可以通过 $k_i$ 打开的箱子获得。

考虑你手上的某种钥匙 $a$，如果你当前拥有数量已经超过需要数量了，显然无影响，否则：

你现在有一个序列 $ka_1, ka_2, ..., ka_m$。可以获取一个 $a$，我们约定 $\forall 1 < i < m_a, ka_i \neq a$。

• 若 $ka_1 \neq a$，则有：

对于需要的 $\forall c$ 钥匙，你现在有一个钥匙种类序列 $kc_1, kc_2, ..., kc_{mc} = c$ 可以获取 $c$，如果序列 $kc$ 中没有 $a$，使用后不影响连通性，否则你考虑找到最大 $j$ 使得 $jk_j$ 使得 $jk_j = kc_j$，若你使用了 $a$，你现在可以使用 $ka_1, ka_2, ..., ka_{j-1}, kc_j, kc_{j+1}, ..., kc_{mc}$ 获取 $c$。

• 若 $ka_1 = a$，则有：

直接用 $a$ 获取 $ka_2$，你发现 $ka_1 \neq a$ 论证仍然成立。

故上述条件充分。

做就直接枚举当前位于哪个箱子，去掉这个箱子后在剩余图上 BFS 即可，时间复杂度 $O(tn^2k)$。

T4-Wei 子与串串（string）

题面

Wei 子现在收到了一个长度为 $n$ 的匹配括号串 $S$，作为图论带师，他凭借这个括号串构想了这样一个带权有向图：

有 $n$ 个节点，点 $i$ 和 $i+1 (1 \leq i \leq n-1)$ 之间互有连边，若 $S_i$ 和 $S_j$ 是匹配的，则 $i,j$ 之间互有连边。

为了评估这个图的复杂性，他现在问你 $q$ 次从他给出的起点 $u$ 走到 $v$ 的最短路是多少。

$1\leq n,q\leq10^5,\forall i,1\leq wl_i,wr_i,wp_i\leq10^6$。

题解

将括号串建树。对于一个满足左右端点匹配的区间 $[l,r]$，建一个虚点 $x$ 并建立 $(x,l),(x,r)$。再递归推出 $[l+1,r-1]$ 区间内的若干不交匹配区间的子树，将 $x$ 连向这些子树的根节点。最后再建一个虚点将建出来的森林的根连起来。

对于一组询问 $S \to T$，考虑求出 $S,T$ 在树上的 LCA $P$。求出 $x,y$ 使得 $x,y$ 是 $P$ 的儿子，且 $S,T$ 分别在 $x,y$ 的子树内。

令 $p_{x}^{'},pr_{x}^{'}$ 表示一个结点 $x$ 所代表区间的左、右端点。显然 $S \to T$ 的路径一定满足 $S \to p_{x}^{'}/pr_{x}^{'} \to p_{y}^{'}/pr_{y}^{'} \to T$。

现在的一个问题在于求出一个结点儿子之间的最短路。情况如下图。

如果边权皆为 1 我们就容易用前缀和得到答案。否则就需要将所有匹配括号 $(p_{x}^{'},pr_{x}^{'})$ 间的边权更新为它们之间的最短路才能保证正确性。这个可以在树上从下往上再从上往下转移。

接下来我们只需要求出一个点到其某个祖先（或者反向）的最短路。设 $f_{u,k,0/1,0/1,0/1}$ 表示起点为 $u$ 或 $u$ 的 $2^k$ 级祖先，$u$ 结点的左/右端点与 $u$ 的 $2^k$ 级祖先的左/右端点的最短路，可以倍增转移。